Bienvenue dans la Leçon 3 de Concepts d'Intelligence Artificielle (PolyU COMP5511). Au cours de cette session, nous passons de la recherche de chemin pour agent unique à la Recherche Adversariale, où les agents opèrent dans des environnements multi-agents compétitifs. Nous introduisons également les Problèmes de Satisfaction de Contraintes (CSP), un paradigme où le but est de trouver un état qui satisfait un ensemble spécifique de restrictions plutôt qu'un chemin.
Concepts Clés
- Recherche Adversariale : Se concentre sur des algorithmes tels que Minimax et Élagage Alpha-Bêta pour prendre des décisions rationnelles contre un adversaire intelligent.
- Recherche Arborescente Monte Carlo (MCTS) : Explore la prise de décision probabiliste, servant de base aux IA de jeu modernes comme AlphaGo.
- Satisfaction de Contraintes : Modélise des problèmes en utilisant des Variables, des Domaines et des Contraintes, résolus par Retour sur Trace et Recherche Locale.
Analyse de Complexité
Dans les contextes adversarials, la complexité de l'espace de recherche est souvent définie par le facteur de branchement du jeu
Attention Changement de Paradigme
Contrairement à la recherche standard (par ex., A* ou BFS) où l'environnement est statique, Recherche Adversariale suppose que l'environnement (l'adversaire) essaie activement de minimiser votre succès. Dans les CSP, l'ordre des actions importe moins que la validité de l'affectation finale.
Pseudocode Conceptuel : Types d'Agents
1
# Agent Adversarial (Théorie des Jeux)
2
fonctionDécider_Mouvement( état):
3
retournerMaximiser_Utilité( Prédire_Minimisation_Adversaire( état))
4
5
# Solveur CSP (Logique de Contrainte)
6
fonctionRésoudre_CSP( variables, contraintes):
7
siToutes_Contraintes_Satisfaites( affectation):
8
retourneraffectation
9
sinon :
10
retournerRecherche_Retour_Trace( variables )
Feuille de Route du Cours
Transition de la Recherche (Leçon 2) à la Prise de Décision Stratégique (Leçon 3).